package 动态规划.打家劫舍;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/1/22 16:28
 */
public class 打家劫舍III {

    // 因为这个题 涉及到 图.树 的， 所以 这几 在 lc 上面 进行编码
    //  不加 缓存表  会 TLE
    public int recursion(TreeNode node,Map<TreeNode,Integer> map){
        // 判断一下 判断过 没有，如果判断过，直接 返回
        if(map.containsKey(node)){
            return map.get(node);
        }
        if(node == null){
            return 0;
        }
        // rob 'root'
        int ans1 = node.val,ans2 = 0;
        if(node.left != null){
            ans1 += recursion(node.left.left,map)+ recursion(node.left.right,map);

        }
        if(node.right != null){
            ans1 += recursion(node.right.left,map) + recursion(node.right.right,map);
        }
        // not rob root
        ans2 += recursion(node.left,map) + recursion(node.right,map);
        // 加入 缓存表中
        int ans = Math.max(ans1,ans2);
        map.put(node,ans);
        return ans;
    }


    // 简单的分析 一下 是 有 重复的子过程的！
    public int solution(TreeNode node ){
        Map<TreeNode,Integer> map = new HashMap<>();
        return recursion(node,map);
    }

    // 关键 是想明白 , 这个 向 左右 子树的 返回值!
    // 上面那种写法是 在递归的过程中 加入 了 缓存 cache 表
    // 下面 这种写法 就是真正的 树形 dp , 时间复杂度 是一样的, 但是常数 时间 少一些
    // dp[0] : 不偷 头节点 max   dp[1] : 偷 头节点的 max
    public int[] treeDp(TreeNode node){
        if(node == null){
            // return new int[2]; 和下面是 等效的！
            return new int[] {0,0};
        }
        int[] leftState = treeDp(node.left);
        int[] rightState = treeDp(node.right);
        int[] dp = new int[2];
        dp[0] = Math.max(leftState[0],leftState[1]) + Math.max(rightState[0],rightState[1]);
        dp[1] = leftState[0] + rightState[0] + node.val;
        return dp;
    }

    public int solutionDP(TreeNode node){
        int[] ints = treeDp(node);
        return Math.max(ints[0],ints[1]);
    }



    // tree
    private class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }



    /*
     如果代码超时， 只能说明一件事情， 当前的这种递归式存在重复子过程
     来回计算， 虽然这道题的重复子过程非常的隐蔽， 但是还是 可以看出来的！
     无论是 用数组 还是  用 map ， 本质上都是再对 走过的子过程进行一个  缓存，
     还是缓存的思想： 缓存： 典型的空间换取时间
     */
    public int memo(TreeNode node,Map<TreeNode,Integer> dp){
        if(node ==  null){
            return 0;
        }
        if(dp.containsKey(node)){
            return dp.get(node);
        }

        // 两种决策， 1. 选择 头节点  2. 不选择 头节点
        // 典型的 dp

        int ans1 = node.val, ans2 = 0;
        // choose  curNode , 那其 左右子节点， 就不能再选了
        if(node.left != null){ // 前提 是 有左右子节点
            ans1 += memo(node.left.left,dp) + memo(node.left.right,dp);
        }
        if(node.right != null){
             ans1 += memo(node.right.left,dp) + memo(node.right.right,dp);
        }


        // no choose  cueNode
        ans2 = memo(node.left,dp) + memo(node.right,dp);
        return dp.put(node,Math.max(ans1,ans2));
    }



    @Test
    public void test(){
        Map<Integer,Integer> map = new HashMap<>();
        Integer put = map.put(10, 20);
        System.out.println(put);
        Integer put1 = map.put(10, 0);
        System.out.println(put1);
    }
}
